skip to main content

Explore Research Products in the NSF-PAR

  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Creators/Authors contains: "Sleator, Daniel D"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ; ( , Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings)
    We give offline algorithms for processing a sequence of 2- and 3-edge and vertex connectivity queries in a fully-dynamic undirected graph. While the current best fully-dynamic online data structures for 3-edge and 3-vertex connectivity require O(n^{2/}3) and O(n) time per update, respectively, our per-operation cost is only O(logn) , optimal due to the dynamic connectivity lower bound of Patrascu and Demaine. Our approach utilizes a divide and conquer scheme that transforms a graph into smaller equivalents that preserve connectivity information. This construction of equivalents is closely-related to the development of vertex sparsifiers, and shares important connections to several upcoming results in dynamic graph data structures, including online models. 
    more » « less
    Accepted Manuscript Full Text Available
  2. ; ; ( , Algorithms and Data Structures - 16th International Symposium, {WADS} 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings)
    Full Text Available